package com.caochenlei.graph;

import java.util.*;

public class FloydSP {
    //键：代表边、值：代表最后一次更新的路径v12、v23，当然也可能为空
    private Map<DirectedEdge, List<DirectedEdge>> edges;
    private EdgeWeightedDigraph digraph;

    public FloydSP(EdgeWeightedDigraph G) {
        edges = new HashMap<>();
        digraph = G;
        //初始化所有的边，包括不可达的边
        for (int from = 0; from < G.size(); from++) {
            for (int to = 0; to < G.size(); to++) {
                if (from == to) {   //自己到自己的总权重为0
                    edges.put(new DirectedEdge(from, to, 0), new ArrayList<>());
                } else {            //自己到不可达总权重为INFINITY
                    edges.put(new DirectedEdge(from, to, Double.POSITIVE_INFINITY), new ArrayList<>());
                }
            }
        }
        //删除图中已有边，再重新加已有边
        for (DirectedEdge edge : G.edges()) {
            edges.remove(getEdge(edge.from(), edge.to()));
            //注意：Arrays.asList(edge, edge)这个加入两次edge目的是为了方便pathTo方法
            edges.put(edge, Arrays.asList(edge, edge));
        }
        //v1：起点、v3：终点、v2：转折点
        for (int v2 = 0; v2 < G.size(); v2++) {
            for (int v1 = 0; v1 < G.size(); v1++) {
                for (int v3 = 0; v3 < G.size(); v3++) {
                    //如果起点、终点和转折点都是自己，那就没必要往下比较了，浪费
                    if (v1 == v2 || v2 == v3 || v1 == v3) continue;
                    DirectedEdge v12 = getEdge(v1, v2);//获取v1->v2的边
                    DirectedEdge v23 = getEdge(v2, v3);//获取v2->v3的边
                    DirectedEdge v13 = getEdge(v1, v3);//获取v1->v3的边
                    //如果确实有一个点使得从v1->v2->v3的总权重小于v1->v3的总权重
                    //那就代表需要重新更新v13的总权重以及最后的v12、v23两条边
                    if (v12.weight() + v23.weight() < v13.weight()) {
                        edges.remove(v13);
                        edges.put(
                                new DirectedEdge(v1, v3, v12.weight() + v23.weight()),
                                Arrays.asList(v12, v23)
                        );
                    }
                }
            }
        }
    }

    //从edges这种结构中获取指定的边对象
    private DirectedEdge getEdge(int from, int to) {
        for (DirectedEdge edge : edges.keySet()) {
            if (edge.from() == from && edge.to() == to) {
                return edge;
            }
        }
        return null;
    }

    //获取从顶点from到顶点to的总权重
    public double distTo(int from, int to) {
        DirectedEdge edge = getEdge(from, to);
        return edge == null ? 0 : edge.weight();
    }

    //判断从顶点from到顶点to是否可达
    public boolean hasPathTo(int from, int to) {
        return distTo(from, to) < Double.POSITIVE_INFINITY;
    }

    //找出从顶点from到顶点to具体路线
    public List<DirectedEdge> pathTo(int from, int to) {
        //判断从顶点from到顶点to是否可达
        if (!hasPathTo(from, to)) {
            return null;
        }
        //找到从顶点from到顶点to路线集合
        List<DirectedEdge> paths = new ArrayList<>();
        for (List<DirectedEdge> list = edges.get(getEdge(from, to));
             !list.isEmpty();
             list = edges.get(getEdge(list.get(0).from(), list.get(0).to()))) {
            DirectedEdge edge = list.get(0);
            //如果此时这条边在原来的图中出现了，并且在paths集合中没有出现，我们才加入到paths
            if (contains(edge.from(), edge.to()) && !paths.contains(edge)) {
                paths.addAll(list);
            }
            //如果此时相等应该退出左循环，否则会造成死循环
            if (edges.get(edge).get(0) == list.get(0)) break;
        }
        for (List<DirectedEdge> list = edges.get(getEdge(from, to));
             !list.isEmpty();
             list = edges.get(getEdge(list.get(1).from(), list.get(1).to()))) {
            DirectedEdge edge = list.get(1);
            //如果此时这条边在原来的图中出现了，并且在paths集合中没有出现，我们才加入到paths
            if (contains(edge.from(), edge.to()) && !paths.contains(edge)) {
                paths.addAll(list);
            }
            //如果此时相等应该退出右循环，否则会造成死循环
            if (edges.get(edge).get(1) == list.get(1)) break;
        }
        //对已经找到的路线进行按顺序排序
        List<DirectedEdge> result = new ArrayList<>();
        for (int i = 0; i < paths.size(); i++) {
            for (DirectedEdge path : paths) {
                if (path.from() == from) {
                    result.add(path);
                    from = path.to();
                }
            }
        }
        return result;
    }

    //判断指定边在原来图中是否存在
    public boolean contains(int from, int to) {
        for (DirectedEdge edge : digraph.edges()) {
            if (edge.from() == from && edge.to() == to) {
                return true;
            }
        }
        return false;
    }
}
